Nondeterministic Finite Automaton

释义 Definition

非确定性有限自动机（NFA）：一种用于描述与识别正规语言（regular languages）的抽象计算模型。它在读入同一个输入符号时，可以从同一状态“同时”选择多个可能的转移（也可包含不消耗输入符号的 ε-转移）。当存在至少一条路径能在读完整个输入后到达接受状态时，该输入被接受。
（提示：该术语还有一些相近表述，如 nondeterministic finite-state automaton。）

发音 Pronunciation (IPA)

/ˌnɒn.dɪˌtɜː.mɪˈnɪs.tɪk ˈfaɪ.naɪt ˌɔː.tɒˈmeɪ.tən/

词源 Etymology

• **non-**：表示“非、不”。
• deterministic（确定性的）：来自 determine（决定、确定）。
• finite（有限的）：表示状态数量是有限个。
• automaton（自动机）：源自希腊语 automatos，意为“自发的、自动的”。
  合起来即“非确定性的、状态有限的自动机”。

例句 Examples

An NFA can have more than one transition for the same input symbol.
NFA 对同一个输入符号可以有不止一条转移。

In automata theory, every nondeterministic finite automaton can be converted into an equivalent deterministic finite automaton that recognizes the same language.
在自动机理论中，任意一个非确定性有限自动机都可以转换为等价的确定性有限自动机，并识别同一种语言。

相关词 Related Words

• Automaton
• Deterministic
• Deterministic Finite Automaton
• Epsilon Transition
• Finite-State Machine
• Regular Language
• Regular Expression
• Subset Construction

文学与经典教材中的出现 Literary Works

• Introduction to the Theory of Computation（Michael Sipser）
• Introduction to Automata Theory, Languages, and Computation（Hopcroft, Motwani, Ullman）
• Automata and Computability（Dexter C. Kozen）
• Compilers: Principles, Techniques, and Tools（Aho, Lam, Sethi, Ullman；“龙书”，讨论词法分析与自动机）